/*
https://leetcode.cn/problems/number-of-2s-in-range-lcci/
面试题17.06.2出现的次数
数论
*/

class Solution {
public:
    int numberOf2sInRange(int n) {
        if (n < 2) return 0;
        if (n < 12) return 1;

        int len = ceil(log10(n + 1));
        int base = pow(10, len - 1), hi = n / base;

        int cnt_hi = (hi == 2) ? (n % base + 1) :
                           ((hi > 2) ? base : 0);
                           //起计算1出现的次数，这题需要额外注意cnt_hi不等于2时情况的处理。
        int cnt_others = hi * (len - 1) * (base / 10);

        return cnt_hi + cnt_others + numberOf2sInRange(n % base);
    }
};